COMPRESSION DES DONNÉES


COMPRESSION DES DONNÉES
COMPRESSION DES DONNÉES

COMPRESSION DES DONNÉES

On peut chercher à rendre minimale la longueur d’un message en codant celui-ci. Si, après décodage, on retrouve exactement le message initial, on dit que le code est réversible, ou bijectif. Ce type de codage est nécessaire pour des messages de type textuel (il est évidemment interdit de perdre ou même d’altérer un caractère alphanumérique dans le cas, par exemple, de la transmission de données financières ou boursières, ou encore d’horaires d’avions). Dans la compression de données, toute perte d’information est donc interdite, à la différence du compactage de données.

De manière générale, pour la compression de données, la seule méthode utilisable pour réduire la longueur d’un message est de tenter de trouver un code dont la redondance soit aussi faible que possible (la redondance peut être définie comme l’action de fournir plus d’information qu’il n’en est nécessaire pour définir un objet, dans le but d’éviter l’ambiguïté ou l’erreur).

Une méthode très efficace de réduction de la redondance par un codage approprié a été proposée par David Albert Huffman au début des années 1950. Schématiquement, cette méthode consiste à faire une liste des n symboles utilisés dans le message dans l’ordre décroissant de leur probabilité d’apparition (fréquence d’apparition/nombre de symboles du message). On crée alors, à partir de cette liste, une deuxième liste en additionnant les probabilités d’apparition des deux derniers symboles de la liste initiale, en supprimant celles-ci, et en les remplaçant par leur somme. Cela fait, on ordonne cette nouvelle liste (qui comporte maintenant n 1 symboles) et on recommence l’opération précédente sur cette nouvelle liste jusqu’à obtenir finalement une liste ne comportant plus que deux nombres. On affecte alors 1 à l’un des nombres et 0 à l’autre. On reprend ensuite les listes successives dans l’ordre inverse où elles ont été établies et, chaque fois qu’une probabilité d’une liste est la somme de deux probabilités d’une liste précédente, on affecte respectivement 1 et 0 à chacune des probabilités formant cette somme, jusqu’à ce qu’on revienne à la liste initiale des symboles. Pour chaque symbole, on aura alors son code binaire en juxtaposant les 1 et les 0 que l’on rencontre en allant de ce symbole jusqu’à la liste située à l’autre extrémité et qui ne comporte que deux nombres.

Le gain en temps de transmission apporté par le codage de Huffman est d’autant plus important que l’on connaît avec plus de précision la fréquence d’apparition de tous les symboles de l’alphabet utilisé, mais cela suppose qu’on explore une première fois le message pour dresser la liste des probabilités des symboles avant de déterminer le code de Huffman pour chaque symbole. Il en résulte que le destinataire ne peut connaître le code utilisé, puisque celui-ci dépend du message; il ne peut donc pas décoder le message. Il faut donc nécessairement faire précéder l’envoi du message d’un «en-tête» donnant le code de chaque symbole, ce qui a pour effet d’allonger le temps de transmission. On reperd ainsi, en partie ou en totalité (selon la longueur du message), le temps gagné grâce au codage de Huffman! Une solution consiste à utiliser une table de codage universelle établie une fois pour toutes pour la langue du message, ce qui évite l’envoi du code mais donne, en revanche, des gains extrêmement variables, pouvant aller jusqu’à des pertes, selon la teneur du message (textes littéraires, factures, dossiers médicaux, liste de statistiques, bulletins météorologiques, etc.).

Durant les vingt années qui ont suivi la parution de l’article de Huffman, l’essentiel des travaux dans ce domaine a porté sur diverses variantes de ce codage, et ce n’est qu’à partir de la publication, en 1977, d’un article de deux chercheurs israéliens, Abraham Lempel et Jacob Ziv, suivi en 1978 d’un nouvel article des deux mêmes chercheurs, que les travaux sur la compression, fondés sur ce que l’on a appelé l’algorithme LZ, d’après les noms des deux auteurs, ont pris un nouveau départ. Le principe qui sous-tend l’algorithme LZ est celui du codage à base de dictionnaire . Schématiquement, considérons un dictionnaire de 500 pages avec 100 mots par page. Pour coder un mot, on peut soit coder séparément chacune de ses lettres, auquel cas il faut 7 bits par lettre et, les mots en français ayant une longueur moyenne de 5 lettres, cela conduit à 35 bits par mot en moyenne, soit indiquer le numéro de la page (9 bits) et le numéro d’ordre du mot dans la page (7 bits), ce qui conduit à 16 bits pour coder n’importe quel mot du dictionnaire: on obtient ainsi un gain supérieur à 2.

Toutefois, ce mode de codage statique (dictionnaire fixe) serait peu commode car il faudrait stocker un dictionnaire de 50 000 mots dans la mémoire de l’ordinateur servant à coder (ou à décoder), ce qui prendrait une place considérable, sans parler de la lenteur du codage due au temps d’accès à cette masse importante de données pour chaque mot et sans compter qu’il faudrait changer de dictionnaire chaque fois que l’on change de langue.

En réalité, l’algorithme LZ est un algorithme adaptatif, c’est-à-dire qu’il construit pour chaque message un dictionnaire, qui est, à chaque instant, fonction de la partie du message qu’il a lue, en même temps qu’il utilise ce dictionnaire pour coder la suite du message. Cela entraîne un avantage supplémentaire puisque, du côté du destinataire, ce même algorithme est utilisable en décodage sans aucune information supplémentaire car l’algorithme est capable de reconstruire une copie exacte du dictionnaire de l’émetteur au fur et à mesure de la réception du message compressé.

Cet algorithme a rencontré presque immédiatement un grand succès puisque, un an seulement après sa publication, le logiciel Compress, initialement développé en langage C sur les ordinateurs Vax de Digital Equipment, était disponible pour toutes les machines sous système d’exploitation Unix, tandis qu’il devenait rapidement disponible sur les micro-ordinateurs, avec diverses variantes et sous différents noms, avec des taux de compression atteignant couramment et dépassant parfois 50 p. 100.

On a vu que la compression de données exigeait entre l’émetteur et le destinataire un minimum d’entente préalable sur les logiciels à utiliser, ce qui a pour effet de compliquer singulièrement les communications. Cette difficulté a conduit certains organismes (privés et publics) à proposer des normes qui soient indépendantes des utilisateurs. C’est ainsi que presque tous les modems sont équipés de puces assurant la compression de données au vol soit selon la norme MNP-5 (algorithme de Huffman adaptatif), soit selon la recommandation V-42 bis du Comité consultatif international télégraphique et téléphonique (C.C.I.T.T.; algorithme de type LZ), et les mettent en œuvre de manière automatique, c’est-à-dire sans aucune intervention des utilisateurs et même, à la limite, à leur insu.

Encyclopédie Universelle. 2012.

Regardez d'autres dictionnaires:

  • Compression De Données — La compression de données est l opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, et qui contient les mêmes informations, en utilisant un algorithme particulier. La décompression est l… …   Wikipédia en Français

  • Compression de donnees — Compression de données La compression de données est l opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, et qui contient les mêmes informations, en utilisant un algorithme particulier. La… …   Wikipédia en Français

  • compression de donnees —  Des donnees textuelles comportent souvent des regularites, soit dans les phrases, soit dans les mots. Grace a des conventions de codification bien choisies il est possible de les exploiter en vue de diminuer la taille de ces donnees. Pour cela,… …   Glossaire de linguistique computationnelle

  • Compression de données — La compression de données ou codage de source est l opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, contenant les mêmes informations, en utilisant un algorithme particulier. Il s agit d… …   Wikipédia en Français

  • Compression de données audio —  Ne pas confondre avec la compression dynamique. La compression audio est une forme de compression de données. Celle ci a pour but de réduire la taille d un fichier audio afin de répondre au besoin de bande passante de la transmission des… …   Wikipédia en Français

  • Compression de données universelle — Un compresseur sans perte universel ne peut pas exister. Plus précisément, pour tout compresseur sans perte, on est certain que : il est impossible de compresser strictement tous les mots ; s il existe un mot qui est strictement… …   Wikipédia en Français

  • Format des données — Format de données Le format des données est la manière utilisée en informatique pour représenter des données sous forme de nombres binaires. C est une convention (éventuellement normalisée) utilisée pour représenter des données, soit des… …   Wikipédia en Français

  • Transmission des données — Transmission de données La transmission de données désigne le transport de quelque sorte d information que ce soit, d un endroit à un autre. Historiquement, cela se faisait par courrier papier, une chaîne de feux ou de sémaphores, puis le Morse… …   Wikipédia en Français

  • Cryptage des données — Cryptographie La machine de Lorenz utilisée par les Allemands durant la Seconde Guerre mondiale pour chiffrer les communications militaires de haut niveau La cryptographie est une des disciplines de la cryptologie s attachant à protéger des… …   Wikipédia en Français

  • Taux de compression de données — Le taux de compression est une mesure de la performance d un algorithme de compression de données informatiques. Il est généralement exprimé en pourcentage, et noté τ. Deux définitions sont communément admises : L une définit le taux de… …   Wikipédia en Français